﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmThinks.DynamicProgramming
{
    /// <summary>
    /// 有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?
    /// </summary>
    public class Question1
    {
       public static System.Collections.Hashtable hash = new System.Collections.Hashtable();
        /// <summary>
        /// 递归算法（时间复杂度O(n2) 空间复杂度O(1)）
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Action1(int n)
        {
            if (n > 0 && n <= 2)
            {
                return n;
            }
            return Action1(n - 1) + Action1(n - 2);
        }
        /// <summary>
        /// 动态规划（时间复杂度O(n) 空间复杂度O(n)）
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static long Action2(int n)
        {
            if (n > 0 && n <= 2)
            {
                return n;
            }
           
            if (hash[n] != null)
            {
                return Convert.ToInt64(hash[n]);
            }

            hash[n]= Action2(n - 1) + Action2(n - 2);
            return Convert.ToInt64(hash[n]);
        }

        public static long last1 = 0;//上一次值
        public static long last2 = 0;//上两次值
        /// <summary>
        /// 优化空间后的动态规划算法时间复杂度O(n) 空间复杂度O(2
        /// </summary>
        /// <param name="n">)</param>
        /// <returns></returns>
        public static long Action3(int n)
        {
            last2 = last1;
            if (n > 0 && n <= 2)
            {
                last1 = n;
                
            }
            else
            {
                last1 = Action3(n - 1) + Action3(n - 2);
             
            }
            return last1;
        }
        /// <summary>
        /// 顺序计算时间复杂度O(n) 空间复杂度O(2
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static long Action4(int n)
        {
            long one = 1;
            long two = 0; 
            for(var i = 0; i < n-1; i++)
            {
                long t=one + two;
                two = one;
                one = t;
            }
            return one;
        }

    }
}
